\subsection*{Problema y solución}

El problema consiste en encontrar un valor entero para $a$ y $b$ dados $T$
valores de entrada. A partir de estos dos valores se pueden generar los $T$
valores de salida siguiendo la ecuación de congruencia, definida de la
siguiente manera:

$$X_k \equiv aX_{k-1} + b\ (10001)$$

Como los valores de entrada están intercalados con los de salida y definidos
sobre los impares, el problema se transforma en hallar el par $(a,b)$ que
resuelve las $T$ ecuaciones, de la siguiente forma:

$$X_k \equiv aX_{k-2} + b + b\ (10001)$$

Como 10001 no es un número primo ($10001 = 137\times 73$), esto se puede
llevar, por el teorema chino del resto, a hallar el par $(a,b)$ que cumple con
las siguientes 2 ecuaciones:

$$X_k \equiv aX_{k-2} + b + b\ (137)$$
$$X_k \equiv aX_{k-2} + b + b\ (73)$$


\subsection*{Detalles de Implementación}

Para hallar la solución utilizamos una versión simple del algoritmo que busca
en el espacio del anillo de $Z-10001$ el par de valores que hacen verdaderas
las $T$ ecuaciones. Como puede existir más de una solución, tomamos el primer
par válido que cumpla para computar el output. Para agilizar los cálculos, a
medida que ingresamos el input de los valores precalculamos el módulo 73 y 137
de esos valores, con el fin de que los factores utilizados en las cuentas sean
más pequeños. Además buscamos una manera eficiente para
calcular el módulo del valor de la iteración actual. Luego resta verificar que
los valores testeados en la iteración sean el par de valores buscados, y
calcular a partir de ellos los valores de salida.


\subsection*{Análisis de complejidad}

Esta versión del algoritmo recorre de manera lineal para $a$ y $b$ los valores
posibles módulo 10001, y luego verifica para cada par que efectivamente cumpla
las $T$ ecuaciones de congruencia. El orden final del algoritmo es de
$O(TN^2)$, donde $T$ es el número de casos de test y $N$ es el valor del módulo.
